1. Field of the Invention
The present invention relates to a system applicable to production, administration, management, etc., and more specifically to a combinatorial optimization system for optimizing an objective function in the combination of a plurality of elements.
2. Description of the Related Art
Conventional systems process various combinatorial optimization problems, such as scheduling problems. An example of a scheduling problem is a job shop problem.
FIG. 1 is a block diagram for explaining the 4-jobs-3-machines job shop problem. A job shop problem is a problem of effectively deciding job operational order on each machine when job operations are already assigned to corresponding machines. In FIG. 1A, 1 through 4 are four kinds of jobs each comprising three operations 1 through 3. Each operation in each job is assigned to a specific machine. For example, in job 2, operation 1 is assigned to machine 3, operation 2 is assigned to machine 1, and operation 3 is assigned to machine 2. In connection with this, processing time required for executing each operation of each job is also determined. For example, the processing time for operation 1 of job 2 is 7, that for operation 2 is 3, and that for operation 3 is 9.
In a job shop problem, if the sequence of job operations performed by each machine is determined, operations performed in each machine, that is, a schedule, is uniquely determined. FIG. 1B shows an example of a schedule for performing operations belonging to job 1, 4, 2, and 3 in this order in each machine. In FIG. 1B, the order of operations in each machine is represented by three digits. For example, "431" means that this operation is the 3rd operation of job 4 and is performed on machine 1.
In FIG. 1B, the last-terminated operations process "332" ends at time "57". This last-termination time is used as an objective function in a job shop problem. A combinatorial optimization problem is given to minimize the value of this function, that is, the termination time of the last operations. To solve the problem is to determine a sequence of the operations on each machine. In FIG. 1B, in order to terminate the last operation "332" on machine 2, earlier than the present value 57, a termination time of the previous operation "232" on machine 2 must be terminated earlier than present value 47. To do this, the termination time of operation "221" must be shortened. To terminate operation 221 earlier than the present termination time, the previous operation "431" by machine 1 and operation "213" on machine 3 must be terminated earlier. (The rest is performed likewise.) It is obvious that operation "332" cannot be terminated earlier although operation "323" is terminated earlier by machine 3 unless operation "232" is terminated earlier.
FIG. 2 indicates that a value of objective function in a job shop problem depends only on a schedule, which is called a critical path (indicated by bold lines). That is, it indicates that an objective function is locally recognized and processed in a job shop problem. By contrast, in a communication network design problem, for example, the value of an objective function varies when the number of lines changes if the objective function is defined as the sum of the cost of all the communication lines. In this case, the objective function is considered global.
Regardless of a local objective function or a global objective function, combinatorial optimization problems such as job shop problems are referred to as NP complete problems. The NP complete problems are explained below.
For example, in a traveling salesman problem, the general input for the problem contains the number of cities as the problem size and the distances of the cities from one another. The size of the input data is referred to as an input size. Q(In) indicates that a problem Q is provided with the input In of the size n. When an algorithm A is given to solve the problem Q, the necessary number of basic operations to solve Q(In) is represented as f.sub.Q.sup.A (In), and the maximum value of f.sub.Q.sup.A (In) for all the applicable data In is represented as F.sub.Q.sup.A (In). If F.sub.Q.sup.A (In) is represented by a polynomial of n, A is referred to as an algorithm having a good order in its polynomial, and the problem Q having this algorithm is regarded as belonging to class P. It is very difficult to show that the problem Q does not belong to class P. However, a problem which can be considered probably not to belong to class P is referred to as having NP complete. It is clear that many problems belong to this class.
It is hard to solve the problems having the NP integrity, and an efficient approximate algorithm is thus required.
Usually, in a conventional approximate algorithm, a neighbor solution (called "initial solution") obtained somehow is compared with its neighborhood, that is, another solution obtained by modifying the initial solution. If a view of objective function is better than that of initial solution, it replaces the initial solution. This is a well-known method referred to as the "iterative improvement method" (or "hill-climbing method"). Recently suggested was a simulated annealing method which permits modification toward a solution of probably worse evaluation.
Next, the conventional iterative improvement method is explained briefly by referring to FIG. 3.
In FIG. 3 (Prior Art), a solution storing module 1 stores a present solution.
A local searching module 2 generates a neighbor solution by modifying a present solution stored in the solution storing module 1, and then stores the neighbor solution in a neighborhood storing module 3.
The neighborhood storing module 3 stores a neighbor solution.
A modification checking module 4 checks based on an objective function whether or not a neighbor solution generated and stored in the neighborhood storing module 3 is actually an improvement on the present solution. If yes, the new solution replaces the present solution and is stored in the solution storing module 1.
Next, the operation of the conventional iterative improvement method is explained briefly. (1) A solution (initial solution) generated somehow is stored in the solution storing module 1. (2) The local searching module 2 generating a neighbor solution by modifying the present solution stored in the solution storing module 1, and the resultant neighbor solution is stored in the neighborhood storing module 3. (3) The modification checking module 4 compares a newly generated neighbor solution stored in the neighborhood storing module 3 with the solution stored in the solution storing module 1, and then checks by referring to an objective function whether or not the new solution is an improvement. If yes, the solution stored in the solution storing module 1 is replaced with the new solution. (4) If not, the processes (2) and (3) are repeated to obtain an improved solution.
However, when the size of a problem becomes larger in such a conventional method as the above described iterative improvement method, the number of neighbor solutions, which are generated by modifying the present solution, increases greatly, so the time taken for one improvement is prolonged, and the total efficiency deteriorates. Besides, since a solution is rewritten only when an objective function is improved, further improvement cannot be made even though it is not a global optimum solution but a local optimum solution, thereby often resulting in an unsatisfactory solution.